package _16_设计;


public class WordDictionary {

    public static void main(String[] args) {

        WordDictionary v = new WordDictionary();

        v.addWord("mad");
        v.addWord("dad");
        v.addWord("at");
        System.out.println(v.search(".ad"));

    }

    private WordDictionary[] children;

    private boolean isEnd;

    public WordDictionary() {
        children = new WordDictionary[26];
    }

    public void addWord(String word) {
        int lenStr = word.length();

        WordDictionary cur = this;
        for (int i = 0; i < lenStr; i++) {
            char curChar = word.charAt(i);
            int index = curChar - 'a';
            if (cur.children[index] == null) {
                cur.children[index] = new WordDictionary();
            }
            cur = cur.children[index];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        char[] chars = word.toCharArray();
        return dfs(chars, this, 0);
    }

    public boolean dfs(char[] chars, WordDictionary cur, int index) {
        if (index == chars.length) return cur.isEnd;
        char curChar = chars[index];
        WordDictionary[] children = cur.children;
        if (curChar == '.') {
            for (WordDictionary child : children) {
                if (child != null && dfs(chars, child, index + 1)) return true;
            }
            return false;
        } else {
            if (children[curChar - 'a'] == null) return false;
            return dfs(chars, children[curChar - 'a'], index + 1);
        }
    }


}
